home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / nelson / model-2a.c < prev    next >
C/C++ Source or Header  |  1990-05-25  |  6KB  |  189 lines
  1. /*
  2.  * Listing 17 -- model-2a.c
  3.  *
  4.  * This module is an order-1 highest order modeling unit that can
  5.  * be using in conjunction with comp-2.c and expand-2.c to compress
  6.  * and expand files.  It is a very simple implementation of an order-1
  7.  * model, using the same techniques for storing counts as were used
  8.  * in model-1.c.  This means that it uses a lot of memory, around
  9.  * 140 Kbytes, and that it spends a lot of time updating the table.
  10.  * Since it can loop up context tables with a simple index on the
  11.  * context character, it is still pretty fast.
  12.  *
  13.  * Building the compression and expansion programs with this model
  14.  * requires moving up to compact model.
  15.  *
  16.  * Building the compressor:
  17.  *
  18.  * Turbo C:     tcc -w -mc comp-2.c model-2a.c bitio.c coder.c
  19.  * QuickC:      qcl /AC /W3 comp-2.c model-2a.c bitio.c coder.c
  20.  * Zortech:     ztc -mc comp-2.c model-2a.c bitio.c coder.c
  21.  * *NIX:        cc -o comp-2 comp-2.c model-1a.c bitio.c coder.c
  22.  *
  23.  * Building the decompressor:
  24.  *
  25.  * Turbo C:     tcc -w -mc expand-2.c model-2a.c bitio.c coder.c
  26.  * QuickC:      qcl /AC /W3 expand-2.c model-2a.c bitio.c coder.c
  27.  * Zortech:     ztc -mc expand-2.c model-2a.c bitio.c coder.c
  28.  * *NIX:        cc -o expand-2 expand-2.c model-1a.c bitio.c coder.c
  29.  */
  30. #include <stdio.h>
  31. #include <stdlib.h>
  32. #include "coder.h"
  33. #include "model.h"
  34.  
  35. /*
  36.  * *totals[] is an array of pointers to context tables.  The EOF
  37.  * character doesn't get a context table, since we stop encoding
  38.  * as soon as that character appears.  Each context table is
  39.  * an array of ints with indices ranging from -1 to 255.
  40.  */
  41. short int *totals[ 257 ];
  42. /*
  43.  * context is the last character encoded or decoded.  It is
  44.  * used to index to the appropriate context table.  We start the
  45.  * model with an arbitrary context of 0;
  46.  */
  47. int context = 0;
  48. int current_order = 1;
  49. int flushing_enabled=0;
  50. int max_order=1;        /* Here for compatibility, not used */
  51.  
  52. /*
  53.  * To initialize the model, I create all 256 context tables, and
  54.  * set all the counts in the table to 0.  By default, the model
  55.  * starts up in context 0, as if the last byte in was '\0'.  Since
  56.  * each context table is supposed to be indexed from -1 to 255,
  57.  * I increment the pointer to the table in totals[], so that the
  58.  * array can be safely indexed with -1.  The only symbol with a
  59.  * non-zero when the tables are initialized is the ESCAPE code,
  60.  * which is set to a count of 1.
  61.  */
  62. void initialize_model()
  63. {
  64.     int i;
  65.     short int j;
  66.     int array_size;
  67.  
  68.     array_size = sizeof( short int * ) * ( 257 + 1 );
  69.     for ( i = 0 ; i < 257 ; i++ )
  70.     {
  71.         totals[ i ] = (short int *) malloc( array_size ) ;
  72.         if ( totals[ i ] == NULL )
  73.         {
  74.             printf( "Error allocating table space!\n" );
  75.             exit( 1 );
  76.         }
  77.         totals[ i ]++;
  78.     for ( j = -1 ; j <= ESCAPE ; j++ )
  79.         totals[ i ][ j ] = 0;
  80.     totals[ i ][ ESCAPE+1 ] = 1;
  81.     }
  82.     for ( j = -1 ; j <= 257 ; j++ )
  83.         totals[ ESCAPE ][ j ] = j + 1;
  84. }
  85.  
  86. /*
  87.  * When the table is updated, every count above "symbol" needs to
  88.  * be incremented, which is somewhat expensive.  If the counts
  89.  * have become to large, the table needs to be rescaled.  After the
  90.  * rescaling is done, we have to make sure that the ESCAPE count
  91.  * is not set to 0, otherwise we would have a problem. After the
  92.  * update is complete, the context is changed to be the symbol that
  93.  * was just updated, and the order is cranked back up to the maximum.
  94.  */
  95. void update_model( int symbol )
  96. {
  97.     int i;
  98.  
  99.     for ( i = symbol+1 ; i <= 257; i++ )
  100.         totals[ context ][ i ]++;
  101.     if ( totals[ context ][ 257 ] == MAXIMUM_SCALE )
  102.     {
  103.         for ( i = 0 ; i <= 257 ; i++ )
  104.             totals[ context ][ i ] /= 2;
  105.         if ( totals[ context ][ ESCAPE ] == totals[ context][ ESCAPE + 1 ] )
  106.         totals[ context ][ ESCAPE + 1 ]++;
  107.     }
  108.     context = symbol;
  109.     current_order = 1;
  110. }
  111.  
  112. /*
  113.  * Since the context table can be directly indexed with the
  114.  * symbol, getting the low and high counts for the particular
  115.  * symbol is nice and easy.  If we have fallen back to a lower
  116.  * order following an ESCAPE code being emitted, we look at the
  117.  * ESCAPE table, else we look at the table selected by the
  118.  * previous context.  The complication arises if we are currently
  119.  * at the maximum order and the symbol has a count of zero.  If
  120.  * that happens, we select the ESCAPE character instead, and
  121.  * return that information to the calling program.
  122.  */
  123. int convert_int_to_symbol( int c, SYMBOL *s )
  124. {
  125.     int local_context;
  126.  
  127.     if ( current_order == 0 )
  128.         local_context = ESCAPE ;
  129.     else
  130.         local_context = context;
  131.  
  132.     s->scale = totals[ local_context ][ 257 ];
  133.     s->low_count = totals[ local_context ][ c ];
  134.     s->high_count = totals[ local_context ][ c + 1 ];
  135.     if ( s->low_count != s->high_count )
  136.         return( 0 );
  137.     s->low_count = totals[ local_context ][ ESCAPE ];
  138.     s->high_count = totals[ local_context ][ 257 ];
  139.     current_order--;
  140.     return( 1 );
  141. }
  142. /*
  143.  * The symbol's scale is always in the same place, which is nice.
  144.  */
  145. void get_symbol_scale( SYMBOL *s )
  146. {
  147.     if ( current_order == 0 )
  148.         s->scale = totals[ ESCAPE ][ 257 ];
  149.     else
  150.         s->scale = totals[ context ][ 257 ];
  151. }
  152. /*
  153.  * To find the symbol whose low and high values straddle count
  154.  * requires walking through the table until a match is found.
  155.  * This is a lengthy operation, and helps to keep decoding
  156.  * slower than encoding.
  157.  */
  158. int convert_symbol_to_int( int count, SYMBOL *s )
  159. {
  160.     int c;
  161.     int local_context;
  162.  
  163.     if ( current_order == 0 )
  164.         local_context = ESCAPE ;
  165.     else
  166.         local_context = context;
  167.  
  168.  
  169.     for ( c = 257; count < totals[ local_context ][ c ] ; c-- )
  170.         ;
  171.     s->high_count = totals[ local_context ][ c + 1 ];
  172.     s->low_count = totals[ local_context ][ c ];
  173.     if ( c == ESCAPE )
  174.         current_order--;
  175.     return( c );
  176. }
  177.  
  178. /*
  179.  * These stubs are used by some of the more complicated modeling
  180.  * modules.
  181.  */
  182. void add_character_to_model( int c )
  183. {
  184. }
  185.  
  186. void flush_model()
  187. {
  188. }
  189.